package leetcode_day._2021._202105._0110;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/5/5 18:24
 * 删除并获得点数
 * 算法：动态规划
 * 定义一个数组，表示下标代表的数字出现的次数
 * 这样问题就跟打家劫舍一样了
 * 如果选了当前数字，那么前面的数字就不能选了
 * dp[i] = max(dp[i - 1], dp[i - 2] + 数字出现的次数)
 */
public class _05_740 {
    public static void main(String[] args) {
        System.out.println(new _05_740().deleteAndEarn(new int[]{2, 3, 4}));
    }

    public int deleteAndEarn(int[] nums) {
        int max = Integer.MIN_VALUE;
        for (int num : nums) max = max > num ? max : num;
        int[] newNum = new int[max + 1];
        for (int num : nums) ++newNum[num];
        int pre = 0, cur = 0;
        for (int i = 1; i < newNum.length; i++) {
            int tmp = cur;
            int now = pre + i * newNum[i];
            cur = now > tmp ? now : tmp;
            pre = tmp;
        }
        return cur;
    }
}
